package com.my.study.structures.linkedlist;

import lombok.extern.slf4j.Slf4j;

import java.util.Stack;

/**
 * @author Carlos
 * @version 1.0
 * @Description 单链表
 * @date 2021/6/7 22:35
 **/
@Slf4j(topic = "c.SingleLinkedList")
public class SingleLinkedList {
    /**
     * 定义一个头节点，无任何含义
     */
    private HeroNode head = new HeroNode(0, null, null);


    public HeroNode getHead() {
        return this.head;
    }


    public void add(int no, String name, String nickname) {
        // 定义一个辅助节点，用于从头节点开始遍历整个列表
        HeroNode temp = head;
        while (true) {
            // 找到链表最后
            if (temp.next == null) {
                break;
            }
            // 如果没有找到，后移
            temp = temp.next;
        }
        temp.next = new HeroNode(no, name, nickname);
    }

    /**
     * 按顺序添加
     *
     * @param no
     * @param name
     * @param nickname
     */
    public void addOrder(int no, String name, String nickname) {
        HeroNode temp = head;
        HeroNode newNode = new HeroNode(no, name, nickname);
        boolean flag = false;

        while (true) {
            if (temp.next == null) {
                break;
            }

            if (temp.next.no > newNode.no) {
                break;
            } else if (temp.next.no == newNode.no) {
                flag = true;
                break;
            }
            // 后移，遍历链表
            temp = temp.next;
        }

        if (flag) {
            log.debug("已经存在编号为[{}]的英雄", newNode.no);
            throw new RuntimeException("准备插入的英雄已经存在");
        } else {
            newNode.next = temp.next;
            temp.next = newNode;
        }
    }

    public void update(int no, String name, String nickname) {
        HeroNode temp, newNode;
        // 表示是否找到节点
        boolean flag = false;
        if ((temp = head.next) == null) {
            throw new RuntimeException("链表为空");
        }
        newNode = new HeroNode(no, name, nickname);
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newNode.no) {
                flag = true;
                break;
            }

            temp = temp.next;
        }
        // 找到
        if (flag) {
            temp.name = newNode.name;
            temp.nickname = newNode.nickname;
        } else {
            log.debug("没有找到编号为[{}]的节点", newNode.no);
            throw new RuntimeException("没有找到满足条件的节点");
        }
    }


    public void delete(int no) {
        HeroNode temp = head;
        // 表示是否找到节点
        boolean flag = false;

        while (true) {
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }

        if (flag) {
            temp.next = temp.next.next;
        } else {
            log.debug("要删除的节点[{}]不存在", no);
            throw new RuntimeException("要删除的节点不存在");
        }
    }

    public void list() {
        // 判断是否为空
        if (head.next == null) {
            return;
        }
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }

    }


    /**
     * 获取单链表有效节点个数
     *
     * @param head
     * @return
     */
    public int getLength(HeroNode head) {
        HeroNode cur = head.next;

        if (cur == null) {
            return 0;
        }
        int length = 0;
        while (cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }

    /**
     * 查找单链表中的倒数第k个节点
     *
     * 思路：
     * 1、编写一个接受head节点，index的方法，其他head节点为头节点，index代表倒数第index节点
     *    例：index = 1，倒数第1个节点，即尾节点
     * 2、获取链表的有效长度size
     * 3、得到size后，从链表第一个有效节点开始遍历(size - index)个，返回次节点
     *    例：有效节点为3，index为1，遍历到(3-1)=2个节点 返回
     *
     * @param head
     * @param index
     */
    public HeroNode findLastIndexNode(HeroNode head, int index) {
        HeroNode cur;
        if ((cur = head.next) == null) {
            return null;
        }

        int size = getLength(head);
        // 遍历size - index 位置，就是我们倒数的第k个节点
        // 校验index
        if (index <= 0 || index > size) {
            return null;
        }

        for (int i = 0; i < size - index; i++) {
            cur = cur.next;
        }
        return cur;
    }


    /**
     * 反转单链表
     * 思路：
     *  1、定义一个reverseHead = new HeroNode()；
     *  2、从头到尾遍历，每遍历一个节点，将其取出，并放在新链表reverseHead的最前端
     *  3、原来的链表 head.next = reverseHead.next
     *
     * @param head 原链表头节点
     * @retrun 反转后的链表头节点
     *
     */
    public void reverse(HeroNode head) {
        HeroNode reverseHead, cur, next;
        // 如果当前链表为空，或者只有一个节点，无需反转，直接返回
        if ((cur = head.next) == null || head.next.next == null) {
            return;
        }
        reverseHead = new HeroNode(0, "", "");

        // 每遍历一个节点，将其取出，并放在新链表reverseHead的最前端
        while (cur != null) {
            // 保存当前节点的下一个节点
            next = cur.next;
            // 将cur的下一个节点指向新链表的最前端，即插入到头结点后面(头插法)
            cur.next = reverseHead.next;
            // 将cur连接到新的链表上
            reverseHead.next = cur;
            // 后移cur
            cur = next;
        }
        head.next = reverseHead.next;
    }


    /**
     * 逆序打印单链表
     * 思路：
     * 1、先将单链表 反转再遍历（会破坏原来链表结构） -》不建议
     * 2、利用栈stack进行反转
     *
     */
    public void reversePrint(HeroNode head) {
        HeroNode cur;
        if ((cur = head.next) == null) {
            return;
        }
        Stack<HeroNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        // 打印
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }
    }



    class HeroNode {
        private int no;
        private String name;
        private String nickname;
        // 指向下一个节点
        private HeroNode next;

        public HeroNode(int no, String name, String nickname) {
            this.no = no;
            this.name = name;
            this.nickname = nickname;
        }

        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
}
